% Calculates the number of spanning trees in a graph G
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function numSpanningTrees = countSpanningTrees(G,varargin);
%  
%   This function will calculate the number of spanning trees in any input
%   graph G.  It uses Kirchhoff's matrix tree theorem to perform this
%   calculation quickly
%
%   INPUTS:     G - adjacency matrix for graph G
%
%   OUTPUTS:    numSpanningTrees - number of spanning trees in G         
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function numSpanningTrees = countSpanningTrees(G,varargin);

% First let's make a new matrix equal to adjacency but -1 instead of 1
laplacian = -1 * G;

% now we need to traverse down the diagonal and set that to the degree of 
% each vertex of G
[xmax ymax] = size(G);
s = sum(G);
for x = 1:xmax
	laplacian(x,x) = s(x);
end;

% % Alternate method to calculate # of spanning trees
 Gp = zeros(xmax - 1,ymax - 1);
 for x = 1:(xmax - 1)
     for y = 1:(ymax - 1)
         Gp(x,y) = laplacian(x,y);
     end;
 end;

% We have the laplacian matrix.  Now we need the Eigenvalues for it
numSpanningTrees = det(Gp);

% d = real(eig(laplacian));
% 
% % Now we just need to multiply all of the eigenvalues together with 1/n, where I guess n is the number of vertices
% % Can't tell if I need to ignore the eigenvalues of effectively zero
% numSpanningTrees = 1;
% for x = 1:xmax
%     if (d(x) > 0.00001),
%         numSpanningTrees = numSpanningTrees * d(x);
%     end;
% end;
% numSpanningTrees = numSpanningTrees / xmax;

